#include <iostream>
#include <vector>
#include <string>

using namespace std;

// permutation
void do_permutation(const char* input, char* output, vector<bool>& used, size_t pos);

void permutation(const char* str) {
  size_t length = strlen(str);

  char* output = new char[length+1];
  memset(output, '\0', length+1);

  vector<bool> used(length, false);
  do_permutation(str, output, used, 0);

  delete [] output;
}

void do_permutation(const char* input, char* output, vector<bool>& used, size_t pos) {
  if (pos == used.size()) {
    cout << output << endl;
    return;
  }

  for (size_t i = 0; i < used.size(); i++) {
    if (!used[i]) {
      output[pos] = input[i];
      used[i] = true;
      do_permutation(input, output, used, pos+1);
      used[i] = false;
    }
  }
}

void inplace_permutation(char* str, char* cur) {
  if (!str || !cur)
    return;

  if (*cur == '\0')
    cout << str << endl;

  for (char* p = cur; *p != '\0'; p++) {
    iter_swap(cur, p);
    inplace_permutation(str, cur+1);
    iter_swap(cur, p);
  }
}

// combination

void do_combination(const char* input, char* output, size_t in_pos, size_t out_pos, size_t len) {
  if (in_pos == len) {
    cout << output << endl;
    return;
  }
  
  // chose input[in_pos]
  output[out_pos] = input[in_pos];
  do_combination(input, output, in_pos+1, out_pos+1, len);
  output[out_pos] = '\0';

  // do not choose input[in_pos]
  do_combination(input, output, in_pos+1, out_pos, len);
}

void combination(const char* str) {
  size_t length = strlen(str);
  
  char* output = new char[length+1];
  memset(output, '\0', length+1);

  do_combination(str, output, 0, 0, length);
  delete [] output;
}

void combination_through_mask(const char* str) {
  size_t len = strlen(str);
  size_t bound = 1 << len;

  for (size_t mask = 0; mask < bound; mask++) {
    // output a combination
    for (size_t p = 0; p < len; p++) {
      if (mask & (1 << p))
	cout << str[p];
    }
    cout << endl;
  }
}

// Telephone words

char get_char_key(size_t key, size_t place) {
  if (place > 3)
    return '\0';

  static int map[][3] = {
    {'0', '0', '0'},
    {'1', '1', '1'},
    {'A', 'B', 'C'},
    {'D', 'E', 'F'},
    {'G', 'H', 'I'},
    {'J', 'K', 'L'},
    {'M', 'N', 'O'},
    {'P', 'R', 'S'},
    {'T', 'U', 'V'},
    {'W', 'X', 'Y'}
  };

  return map[key][place];
}

void print_tele_words(char* output, const int* nums, size_t len, size_t pos) {
  if (pos == len) {
    cout << output << endl;
    return;
  }

  if (nums[pos] == 0 || nums[pos] == 1) {
    output[pos] = nums[pos] + '0';
    print_tele_words(output, nums, len, pos+1);
  }
  else {
    for (size_t i = 0; i < 3; i++) {
      output[pos] = get_char_key(nums[pos], i);
      print_tele_words(output, nums, len, pos+1);
    }
  }
}

void telephone_words(const int* nums, size_t len) {
  char* output = new char[len+1];
  memset(output, '\0', len+1);

  print_tele_words(output, nums, len, 0);

  delete [] output;
}

double power(double base, size_t exp) {
  if (exp == 0) {
    return 1.0;
  }
  if (exp == 1) {
    return base;
  }
  if (exp & 1) {
    return base * power(base, exp-1);
  }
  else {
    double half = power(base, exp / 2);
    return half * half;
  }
}

int main() {
  cout << "Test permutation" << endl;
  permutation("abc");

  cout << "Test in place permutation" << endl;
  char str[] = "abc";
  inplace_permutation(str, str);

  cout << "Test combination" << endl;
  combination("abc");

  cout << "Test combination through mask" << endl;
  combination_through_mask("abc");

  cout << "Test print telephone words" << endl;
  int nums[] = {4,9,7,1,9,2,7};
  telephone_words(nums, sizeof(nums)/sizeof(int));

  cout << "Test power: " << power(2, 10) << endl;
  return 0;
}
